package com.zhangx.datastructure.tree;

/**
 * @ClassName BiTree
 * @Description 二叉树
 * P178
 * @Author zhangx
 * @Date 2021/1/8 8:48
 **/
public class BiTree {

    Node[] tree;
    int n;//节点数
    int r;//头结点下标

    static class Node{
        String data;
        Node left;
        Node right;

        Node(String data,Node left,Node right){
            this.data = data;
            this.left = left;
            this.right = right;
        }
    }

    public BiTree(){
//        初始化数据
        Node i = new Node("i",null,null);
        Node j = new Node("j",null,null);
        Node k = new Node("k",null,null);

        Node h = new Node("h",null,k);
        Node f = new Node("f",i,null);
        Node g = new Node("g",null,j);

        Node d = new Node("d",h,null);
        Node e = new Node("e",null,null);
        Node b = new Node("b",d,e);
        Node c = new Node("c",f,g);
        Node a = new Node("a",b,c);

        tree = new Node[11];
        tree[0] = a;
        tree[1] = b;
        tree[2] = c;
        tree[3] = d;
        tree[4] = e;
        tree[5] = f;
        tree[6] = g;
        tree[7] = h;
        tree[8] = i;
        tree[9] = j;
        tree[10] = k;

        this.r = 0;
        this.n = tree.length;
    }

    /**
     *  前序遍历法
     */
    public void preOrderTraverse(Node n){
        if (null == n){
            return;
        }
        System.out.println(n.data);
        preOrderTraverse(n.left);
        preOrderTraverse(n.right);
    }

    /**
     * 中序遍历法
     * @param n
     */
    public void inOrderTraverse(Node n){
        if (null == n){
            return;
        }
        inOrderTraverse(n.left);
        System.out.println(n.data);
        inOrderTraverse(n.right);
    }

    /**
     * 后序遍历法
     * @param n
     */
    public void postOrderTraverse(Node n){
        if (null == n){
            return;
        }
        postOrderTraverse(n.left);
        postOrderTraverse(n.right);
        System.out.println(n.data);
    }

    public static void main(String[] args) {
        BiTree biTree = new BiTree();
        biTree.preOrderTraverse(biTree.tree[biTree.r]);
        System.out.println("---------");
//        h k d b e a i f c g j
        biTree.inOrderTraverse(biTree.tree[biTree.r]);
        System.out.println("---------");
        biTree.postOrderTraverse(biTree.tree[biTree.r]);
    }
}
